#include <queue>

using namespace std;

class Solution {
public:
    queue<pair<int, int>> q1;
    queue<pair<int, int>> q2;

    bool m1[100][100];
    bool m2[100][100];

    int direction[8][2] = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 }, { 1, -1 }, { -1, 1 }, { 1, 1 }, { -1, -1 } };

    int n, depth;

    // 双向 BFS，时间复杂度为 O(n^2)
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        n = grid.size();

        if (grid[0][0] == 1 || grid[n - 1][n - 1]) {
            return -1;
        }

        // 如果 size 为 1，不需要双向搜索，提前返回
        if (grid.size() == 1) {
            return 1;
        }

        // 因为从开始和结束节点进行双向搜索，所以初始化经过的格子数为 2
        depth = 2;

        memset(m1, 0, sizeof(m1));
        memset(m2, 0, sizeof(m2));

        q1.push({ 0, 0 });
        q2.push({ n - 1, n - 1 });

        // m 标记是否已访问过
        m1[0][0] = true;
        m2[n - 1][n - 1] = true;

        // 两边分别开始 bfs
        while (!q1.empty() && !q2.empty()) {
            bool v = bfs(grid, q1, m1, m2);

            if (v) {
                return depth;
            }

            v = bfs(grid, q2, m2, m1);

            if (v) {
                return depth;
            }
        }

        return -1;
    }

    int bfs(
        vector<vector<int>>& grid,
        queue<pair<int, int>>& q,
        bool m1[100][100],
        bool m2[100][100]
    ) {
        int size = q.size();

        // 遍历层数相同的所有节点
        for (int j = 0; j < size; j++) {
            auto p = q.front();
            q.pop();

            for (int i = 0; i < 8; i++) {
                int x = p.first + direction[i][0];
                int y = p.second + direction[i][1];

                if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] == 1) {
                    continue;
                }

                // 如果已经在另外一个队列访问过，那么证明找到最短的路径
                if (m2[x][y]) {
                    return true;
                }

                // 如果在当前队列中没有访问过，那么加入到队列并标记已访问
                if (!m1[x][y]) {
                    q.push({ x, y });
                    m1[x][y] = true;
                } 
            }
        }

        depth++;

        return false;
    }
};